In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges, from the original graph, connecting pairs of vertices in that subset.
Definition
Formally, let
be any graph, and let
be any subset of vertices of . Then the induced subgraph
is the graph whose vertex set is
and whose edge set consists of all of the edges in
that have both endpoints in
.
[.] That is, for any two vertices
,
and
are adjacent in
if and only if they are adjacent in
. The same definition works for
,
, and even
.
The induced subgraph may also be called the subgraph induced in by , or (if context makes the choice of unambiguous) the induced subgraph of .
Examples
Important types of induced subgraphs include the following.
-
are induced subgraphs that are paths. The shortest path between any two vertices in an unweighted graph is always an induced path, because any additional edges between pairs of vertices that could cause it to be not induced would also cause it to be not shortest. Conversely, in distance-hereditary graphs, every induced path is a shortest path.
[.]
-
are induced subgraphs that are cycles. The girth of a graph is defined by the length of its shortest cycle, which is always an induced cycle. According to the strong perfect graph theorem, induced cycles and their complement graph play a critical role in the characterization of .
[.]
-
Cliques and independent sets are induced subgraphs that are respectively or .
-
are induced subgraphs that are matchings.
-
The neighborhood of a vertex is the induced subgraph of all vertices adjacent to it.
Computation
The induced subgraph isomorphism problem is a form of the subgraph isomorphism problem in which the goal is to test whether one graph can be found as an induced subgraph of another. Because it includes the
clique problem as a special case, it is
NP-complete.
[.]
